package logic;

import java.util.ArrayList;
import java.util.Arrays;


public class TSPSolver {
	public int k = 20;
	Kattio io = new Kattio(System.in, System.out);
	public static final boolean DEBUG = false;
	public static final boolean SHOWGUI = false;
	private static long time;
	private static long ttime;
	private static ArrayList<String> timeOutput = new ArrayList<String>();
	/**
	 * Method to create a graph from the specific input from standard in
	 * @return
	 */
	public Graph getEuclideanGraph(){
		if(DEBUG){
			time = System.currentTimeMillis();
			ttime = System.currentTimeMillis();
		}
		int n = 0;
		if(io.hasMoreTokens()){
			n = io.getInt();
		}
		int[][] adjMatrix = new int[n][n];
		Vertex[] graphvertices = new Vertex[n];
		if(!(n<1)){
			for(int i=0;i<n;i++){
				Vertex x = new Vertex(io.getDouble(),io.getDouble(), i);
				graphvertices[i] = x;
				for(int j=0;j<i;j++){
					adjMatrix[i][j] = x.getEuclideanDistance(graphvertices[j]);
					adjMatrix[j][i] = adjMatrix[i][j];
				}
			}
		} else {
			System.err.println("Invalid input");
			return null;
		}
		if(DEBUG){
			timeOutput.add("TIME: Graph input and distmatrix: "+(System.currentTimeMillis()-time));
			time = System.currentTimeMillis();
		}
		if(n>1){
			findKList(k, adjMatrix, graphvertices);
		}
		if(DEBUG){
			timeOutput.add("TIME: Creating klist: "+(System.currentTimeMillis()-time));
			time = System.currentTimeMillis();
		}
		return new Graph(graphvertices, adjMatrix);
	}
	
	private void findKList2(int k, int[][] adjMatrix, Vertex[] graphvertices){
		Vertex[] kList; // Possible improvement change to heap
		for(int i = 0; i < graphvertices.length; i++){
			if(graphvertices.length<=k){
				kList = new Vertex[graphvertices.length-1];
			} else {
				kList = new Vertex[k];
			}
			for(int h = 0; h < kList.length; h++){
				int smallest = -1;
				for(int j = 0;j < graphvertices.length;j++){
					if(i == j){
						continue;
					}
					if(smallest == -1){
						if(h == 0){
							smallest = j;
						}
						else if(adjMatrix[i][j] == adjMatrix[i][kList[h-1].index]){
							for(int d = h -1 ; d >= 0; d--){
								if(graphvertices[j] == kList[d]){
									break;
								}
								if(adjMatrix[i][j] != adjMatrix[i][kList[d].index]){
									smallest = j;
									break;
								}
							}
						}
						else{
							if(adjMatrix[i][j] > adjMatrix[i][kList[h-1].index]){
								smallest = j;
							}
						}
					}	
					else{
						if(h == 0){
							if(adjMatrix[i][j] < adjMatrix[i][smallest]){
								smallest = j;
							}
						}
						else{
							if(adjMatrix[i][j] == adjMatrix[i][kList[h-1].index]){
								int temp = -1;
								for(int d = h -1 ; d >= 0; d--){
									if(graphvertices[j] == kList[d]){
										temp = -1;
										break;
									}
									else{
										temp = j;
									}
									if(adjMatrix[i][j] != adjMatrix[i][kList[d].index]){
										temp = j;
										break;
									}
								}
								if(temp != -1){
									smallest = temp;
								}
								
							}
							else{
								if(adjMatrix[i][j] > adjMatrix[i][kList[h-1].index]){
									if(adjMatrix[i][j] < adjMatrix[i][smallest]){
										smallest = j;
									}
								}
							}
						}
					}
					
				}
				kList[h] = graphvertices[smallest];
				smallest = -1;
			}
			graphvertices[i].topk = kList;
			
//			for(Vertex v :kList){
//				System.out.println(adjMatrix[i][v.index]);
//			}
//			System.out.println();
			
		}
	}
	
	private void findKList(int k, int[][] adjMatrix, Vertex[] graphvertices){
		Vertex[] kList; // Possible improvement change to heap
		for(int i = 0; i < graphvertices.length; i++){
			if(graphvertices.length<=k){
				kList = new Vertex[graphvertices.length-1];
			} else {
				kList = new Vertex[k];
			}
			int index = 0;
			int biggest = -1;
			for(int j = 0;j < graphvertices.length;j++){
				if(index < kList.length){
					if(graphvertices[j] != graphvertices[i]){
						kList[index] = graphvertices[j];
						if(biggest == -1){
							biggest = index;
						} else if( adjMatrix[i][kList[biggest].index] < adjMatrix[i][j]){
							biggest = index;
						}
						index +=1;
					}
				} else if( adjMatrix[i][kList[biggest].index]
				                        > adjMatrix[i][j]){
					//swap in kList to new smaller value
					if(graphvertices[j] != graphvertices[i]){
						kList[biggest] = graphvertices[j];
					}
					//find new biggest
					for(int l=0 ; l<kList.length ; l++){
						if(adjMatrix[i][kList[l].index]>adjMatrix[i][kList[biggest].index]){
							biggest = l;
						}
					}
					//finished find new biggest
				}
			}
			
			graphvertices[i].topk = kList;
			if(kList[kList.length-1]==null){
				System.out.println(Arrays.toString(kList));
			}
		}
	}

	//	private void sortNeighbors(Vertex[] graphvertices,
	//			int[][] adjMatrix) {
	//		for(int i=0; i<adjMatrix.length;i++){
	//			Edge[] neighbors = new Edge[graphvertices.length];
	//			for(int j=0 ; j< adjMatrix[i].length ;j++){
	//				neighbors[j] = new Edge(graphvertices[i], graphvertices[j], adjMatrix[i][j]);
	//			}
	//			Arrays.sort(neighbors);
	//			graphvertices[i].neigbors = neighbors;
	//		}
	//	}

	public static void main(String[] args){
		TSPSolver tsp = new TSPSolver();
		tsp.k = 18;
		Graph g = tsp.getEuclideanGraph();
		//Graph only has one node, print it
		if(g.vertices.length==1){
			tsp.io.print(g.vertices[0].index);
			tsp.io.close();
			return;
		}
		// Construct tour
		Tour tour = NN(g);		//Change constructing tour
		
		if(TSPSolver.DEBUG){
			timeOutput.add("TIME: Tour construction: "+(System.currentTimeMillis()-TSPSolver.time));
			TSPSolver.time = System.currentTimeMillis();
		}
		//Optimize tour
		tour = threeOpt(g, tour);		//Change optimizing tour
		if(TSPSolver.DEBUG){
			timeOutput.add("TIME: Optimization: "+(System.currentTimeMillis()-TSPSolver.time));
			TSPSolver.time = System.currentTimeMillis();
		}
		tsp.io.println(tour);
//		tsp.io.println(tour.length());
		tsp.io.close();
		if(SHOWGUI){
//			new GraphGUI(g, tour, false,false);
		}
		if(TSPSolver.DEBUG){
			timeOutput.add("TIME: Total time: "+(System.currentTimeMillis()-TSPSolver.ttime));
			try {
				Thread.sleep(100);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			for(String s:timeOutput){
				System.err.println(s);
			}
		}
	}

	public static Tour origTour(Graph g){
		int[] tour = new int[g.vertices.length];
		for(int i=0;i<tour.length;i++){
			tour[i] = i;
		}
		return new TourArray(tour, g);
	}
	
//	public static Tour RandomTour(Graph g){
//		Vertex[] elements = Arrays.copyOf(g.vertices,g.vertices.length);
//		shuffle(elements);
//		return new TourArray(elements);
//	}
	
	 /**
     * Shuffle an array of type T
     *
     * @param <T> The type contained in the array
     * @param array The array to be shuffled
     */
    private static <T> void shuffle(T[] array) {
            for (int i = array.length; i > 1; i--) {
                    T temp = array[i - 1];
                    int randIx = (int) (Math.random() * i);
                    array[i - 1] = array[randIx];
                    array[randIx] = temp;
            }
    }
	
	public static Tour NN(Graph g){
		return NearestNeighbor.getNNEuclideanTSP(g,0);
	}
	
	public static Tour twoOpt(Graph g, Tour tour){
		return TwoOpt.twoOpt(g,tour);
	}

	public static Tour threeOpt(Graph g, Tour tour){
		return ThreeOpt.threeOpt(g, tour);
	}
	
}